#! /usr/bin/python
""" repeated digits, prime numbers"""
import random
import math

_mrpt_num_trials = 5

def tryComposite(a, s, d, n):
    x = pow(a, d, n)
    if x == 1: return False
    for i in range(s):
	x = pow(a, 2**i * d, n)
	if x == n - 1: return False
    return True

def millerRabin(n):
    s = 0
    d = n - 1
    while(d%2 == 0):
         s += 1
	 d /= 2
    k = 0
    for i in range(_mrpt_num_trials):
	a = random.randrange(2, n)
        if tryComposite(a, s, d, n): return False
    return True

def isPrime(n):
    if n ==2 or n==3 or n==5 or n==7: return True
    if n==1 or n%2 == 0 or n%3 == 0: return False
    for i in range(5, int(math.sqrt(n))+1, 6):
        if n%i == 0 or n%(i+2) == 0: return False
    return True

cycle = [1, 3, 7, 9]

def countRepeats(n, r):
    count = 0
    while n > 0:
	if n%10 == r: count += 1
	n /= 10
    return count

possibleM = [8, 9, 8, 9, 9, 9, 9, 7, 8, 8]

primes = []

def generateComb(d):
    nlist = []
    for i in range(10):
        for pos in range(10):
	    n = (10**(9-pos) - 1)/9*d * 10**(pos+1) + i * 10**pos + (10**pos - 1)/9 * d
	    if n > 10**9 and millerRabin(n): nlist.append(n)	    
    return nlist

matrix = [[] for i in range(10)]
matrix[1] = generateComb(1)
for i in range(3, 8):
    matrix[i] = generateComb(i)

matrix[9] = generateComb(9)
print matrix

for i in range(1, 10):
    for j in (1, 3, 7, 9):
	n = i*10**9 + j
	if millerRabin(n): matrix[0].append(n)
d = 2
for i in (0, 1, 3, 4, 5, 6, 7, 8, 9):
    for pos in range(1, 10):
	for j in (1, 3, 7, 9):
	    n = (10**(10 - pos)/9 - 1) * d * 10**pos + ((10**pos - 1)/9 * d)/10 * 10 + i * 10**pos + j
	    if n < 10**9: break	    
            if millerRabin(n): matrix[2].append(n)

d = 8
for i in (0, 1, 3, 4, 5, 6, 7, 2, 9):
    for pos in range(1, 10):
	for j in (1, 3, 7, 9):
	    n = (10**(10 - pos)/9 - 1) * d * 10**pos + ((10**pos - 1)/9 * d)/10 * 10 + i * 10**pos + j
	    #print n
	    if n < 10**9: break	    
            if millerRabin(n): matrix[8].append(n)

#print primes
print matrix
print sum(sum(matrix[i]) for i in range(10))
